package leetcode_21_40;

public class searchRange_34 {
    /**
     * 非递减顺序排列的整数数组 nums，和一个目标值 target。
     * 找出给定目标值在数组中的开始位置和结束位置
     * 时间复杂度为 O(log n)
     * 思路尝试二分法
     * 最终还是学习了官方解法
     * @param nums
     * @param target
     * @return
     */
    public static int[] searchRange(int[] nums, int target) {
        int leftIdx = binarySearch(nums, target, true);           //第一个大于等于 target的下标
        int rightIdx = binarySearch(nums, target, false) - 1;  //找到的是第一个大于 target的下标
        if (leftIdx <= rightIdx && rightIdx < nums.length && nums[leftIdx] == target && nums[rightIdx] == target) {
            //左值必须小于右值，不越界，又因为查找不一定返回的是准确结果需要判断
            return new int[]{leftIdx, rightIdx};
        }
        return new int[]{-1, -1};
    }

    /**
     * 二分法查找高位或低位第一个对应元素下标
     * 思想是找到匹配的mid值后，依然继续二分遍历完
     * 寻找 leftIdx 即为在数组中寻找第一个大于等于 target的下标，
     * 寻找 rightIdx即为在数组中寻找第一个大于 target的下标
     * @param nums
     * @param target
     * @param lower
     * @return
     */
    public static int binarySearch(int[] nums, int target, boolean lower) {
        int left = 0, right = nums.length - 1, ans = nums.length;
        while (left <= right) {
            int mid = (left + right) / 2;
            if (nums[mid] > target || (lower && nums[mid] >= target)) {
                //找左边第一个，mid值大于等于 target 都可以转向左边区间，此时左区间最少有一个mid处的target值
                //若找右边第一个，mid值只有大于 target 才以转向左边区间，因为此时右边区间才满足完全没有target值
                right = mid - 1;
                ans = mid;
            } else {
                left = mid + 1;
            }
        }
        return ans;
    }

}
